This invention concerns a method and apparatus for correcting errors that occur in transmission of information signals between electronic devices. More specifically, the invention relates to correction of such errors in writing information to and reading information from a disk, tape, or optical drive, and in sending and receiving information via telecommunications equipment, such as point to point transmission of data via a satellite or over a telephone line. However, the methodology applies to error correction of information-containing signals transmitted between any two electronic devices. In addition, the invention concerns a computer-readable medium or signal encoded in accordance with the method.
It is known how to optimally detect data sequences transmitted over noisy telecommunications channels by using the Viterbi algorithm. See generally A. J. Viterbi, "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm," IEEE TRANS. INFO. THEORY, 13:260-269 (April 1967). Useful background on technology for this application is described in C. B. Shung et al., "Area-Efficient Architectures for the Viterbi Algorithm," 1990 IEEE IBM Research Div., Almaden Research Ctr., UC Berkeley; and L. Fredrickson et al., U.S. Pat. No. 5,280,489 (1994), "Time-varying Viterbi detector for control of error event length". The '489 patent discloses a method and apparatus for detecting spectral null sequences on a noisy telecommunications channel, using a Viterbi detector with a so-called trellis structure to create a further, time-varying trellis structure for limiting the maximum length of so-called dominant error events.
In these references, the D-operator (or D-transform) is commonly used for describing channels, filters, and coding operations. As used in this field of art, the D stands for a delay of one unit time. Thus if the clock for a circuit runs at 1 MHz rate, D represents a delay unit whose output follows its input delayed by 1 .mu.sec. In diagrams, a D in a box represents circuitry, such as a delay line or flip-flop, for a time delay of one cycle duration. In mathematical notation, this D-operator also allows a compact description of sequences and filtering operations. In this usage, the notation u(D), for example, represents the polynomial ##EQU1## which is generally known as the D-transform of the time domain sequence u={u.sub.0, u.sub.1, u.sub.2, . . . }. This notation provides a compact way to express that the first member of the sequence is u.sub.0, the second output is u.sub.1, and so on. A known property of D-transforms is that a filter with transfer function f(D) and input u(D) produces the output f(D) u(D), where the product is taken by standard polynomial multiplication.
Recently, several approaches have been proposed for trellis structures utilizing partial response channels with transfer functions of the form (1-D)(1+D).sup.n. See, for example, P. Siegel et al., "An 8/9 rate trellis code for E.sup.2 PR4," presented UC SD CMRR, May 1997; W. Bliss, "An 8/9 rate time-varying trellis code for high-density recordings," INTERMAG 97; I. J. Moon et al., "Maximum transition run codes for data storage systems," IEEE TRANS. MAG., 32:3992-94 (September 1996). When the value of n is 2, the partial response channel is known as EPR4; when the value of n is 3, the partial response channel is known as E.sup.2 PR4. On magnetic storage channels, these approaches are appropriate at relatively high user densities, such as when the ratio of magnetic pulse width at half amplitude (pw.sub.50) to time per user bit is 2.4 or higher. At such high user densities, the most common error event is a failure to detect a sequence of three transitions (tribits) or longer sequences of consecutive transitions. Maximum transition run (MTR) codes such as that of Moon et al., supra, eliminate these error events by eliminating from the signal all sequences of three or more transitions. This expedient is a coding constraint that limits system capacity; the coding constraint limits the code rate to be below the rate 8/9. Therefore these codes incur increased code rate loss at high linear densities, as Z. Kern et al. demonstrate in "Experimental Performance Comparison of FTD/DFE Detectors: 8/9 (O,k) vs. 4/5 MTR Codes," INTERMAG 97.
The codes proposed in P. Siegel et al. and W. Bliss, supra, overcome this code rate limitation by allowing sequences of three transitions at only specified locations within each code word. Tribits are allowed to start on either odd-numbers bits or even-numbered bits, but not both. This approach increases the minimum observed distance between sequences at the detector. The codes proposed in P. Siegel et al. and some of the codes of W. Bliss achieve a code rate of 8/9 by coding in blocks of 16 user bits translated to 18 channel bits. These codes allow tribits but allow no sequences of four transitions (quadbits) or more. However, the coding schemes utilizing relatively long 18-bit block lengths have encoders, decoders, serializers, and deserializers which are relatively complex. Additionally, substantial path memory at the detector is required to insure reliable decisions. When more probable errors occur at boundaries between code words, the worst-case error propagation is 4 user bytes.
In many EPRML and E.sup.2 PRML storage systems, the means of coding data to be recorded is via an encoder followed by a precoder, as in the system proposed by Bliss, supra The encoder output and the precoder input sequence is in binary non-return to zero inverse (NRZI) notation, where a 1 designates the recording of a transition (such as a magnetic transition) and a 0 represents the lack of a transition. The precoder output and channel input is in binary non-return to zero (NRZ) notation, where a 0 represents one level (such as one level of magnetic saturation) and a 1 represents the opposite level. The precoder has transfer function, f(D) =1/(1.sym.D)D), where the symbol .sym. represents XOR, i.e., exclusive OR.
The terms EPRML and E.sup.2 PRML have been applied to EPR4 and E.sup.2 PR4 systems of the general type that this invention concerns. The additional letters "ML" indicate that the system includes a Maximum Likelihood detector. It should be appreciated, however, that the systems of the present invention involve a combination of trellis coding and additional channel constraints in a maximum likelihood detector.
A need exists for a trellis coded EPRML or E.sup.2 PRML system functionally similar to the MTR code systems and at the same time avoiding the increased code rate loss at high linear densities, occurring when those systems exclude all tribits, as in the kind of system proposed by Moon et al., supra. A need also exist for codes of this type which utilize relatively short block lengths, to permit use of simpler encoders, decoders, serializers, and deserializers than those required when using the coding approaches of systems such as those proposed in P. Siegel et al. and the 16/18 codes of W. Bliss. In addition, a need exists for codes which utilize relatively short block lengths to reduce error propagation at code word boundaries to a value below 4 user bytes. Further, a need ezists for coding approaches that will require less path memory to insure reliable decisions at the detector.